package com.heima.leetcode.practice;

/**
 * leetcode 1206 设计跳表
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/20 8:44
 */
public class E1206 {
    public static class SkipList {
        // 跳表的最底层的节点的值是递增的
        private static final int MAX_LEVEL = 15; // 最大层数，redis 默认32层，java中默认62

        private final SkipNode sentinel; // 哨兵节点

        /**
         * 无参构造器初始化
         */
        public SkipList() {
            sentinel = new SkipNode();
        }

        /**
         * 跳表节点
         */
        static class SkipNode{
            int val; // 跳表节点值
            SkipNode[] next; // 下一个节点，下标为层数，层数越高指向的next节点层数越高

            // 每次构造器调用初始化next数组
            // 这里就固定了数组长度为32，不考虑空间占用的因素了
            // 每一层初始化的next都为null
            {
                next = new SkipNode[MAX_LEVEL];
            }

            public SkipNode() {
            }

            public SkipNode(int val) {
                this.val = val;
            }
        }

        /**
         * 查找目标值，返回查找目标值所经过的路径
         * @param target 路径
         * @return 路径
         */
        private SkipNode[] find(int target) {
            SkipNode curr = sentinel; // 从哨兵节点开始查找
            SkipNode[] path = new SkipNode[MAX_LEVEL]; // 路径数组，记录路径
            // 从最高层开始遍历，逐层向下查找，一次for循环处理一层
            for (int level = MAX_LEVEL - 1; level >= 0; level--) {
                // 处理当前层，如果下一个节点不为空且值小于目标值，curr向右移，注意有可能出现同一层可能会移动多次
                while (curr.next[level] != null && curr.next[level].val < target){
                    curr = curr.next[level];
                }
                // 记录路径
                path[level] = curr;
            }
            return path;
        }

        /**
         * 查找目标值
         * @param target 目标值
         * @return 查找到返回true，否则返回false
         */
        public boolean search(int target) {
            SkipNode[] path = find(target);
            return path[0].next[0] != null && path[0].next[0].val == target;
        }

        /**
         * 随机层数，最底层50%，逐层递减
         * @return 随机层数
         */
        private int randomLevel() {
            int level = 1;
            while (Math.random() < 0.5 && level < MAX_LEVEL - 1) {
                level++;
            }
            return level;
        }

        /**
         * 添加目标值
         * @param num 目标值
         */
        public void add(int num) {
            // 1. 查找目标值所经过的路径
            SkipNode[] path = find(num);
            SkipNode node = new SkipNode(num);
            // 2. 随机层数
            int level = randomLevel();
            // 3. 逐层设置next
            for (int i = 0; i < level; i++) {
                node.next[i] = path[i].next[i];
                path[i].next[i] = node;
            }
        }

        /**
         * 删除目标值
         * @param num 目标值
         * @return 删除成功返回true，否则返回false
         */
        public boolean erase(int num) {
            // 1. 查找目标值所经过的路径
            SkipNode[] path = find(num);
            SkipNode node = path[0].next[0];
            // 2. 如果目标值不存在，返回false
            if (node == null || node.val != num) {
                return false;
            }
            // 3. 逐层调整指针
            for (int level = 0; level < MAX_LEVEL; level++) {
                if (path[level].next[level] != node) break;
                path[level].next[level] = node.next[level];
            }
            return true;
        }
    }
}
